package com.zlm.custom.map;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zlm
 * @date 2025/4/26
 */
public class MyHashMap<K,V> {

    Node<K,V>[] table = new Node[16];

    private int size = 0;

    public V put(K key,V value){
        int keyIndex = indexOf(key);
        Node<K, V> kvNode = table[keyIndex];
        if(kvNode == null){
            table[keyIndex] = new Node<>(key,value);
            size++;
            resizeIfNecessary();
            return null;
        }
        while (true){
            if(kvNode.key.equals(key)){
                V oldValue = kvNode.value;
                kvNode.value = value;
                return oldValue;
            }
            if(kvNode.next == null){
                kvNode.next = new Node<>(key,value);
                size++;
                resizeIfNecessary();
                return null;
            }
            kvNode = kvNode.next;
        }

    }

    public V get(K key){
        int keyIndex = indexOf(key);
        Node<K, V> kvNode = table[keyIndex];
        while (kvNode != null){
            if(kvNode.key.equals(key)){
                return kvNode.value;
            }
            kvNode = kvNode.next;
        }

        return null;
    }

    public V remove(K key){
        int keyIndex = indexOf(key);
        Node<K, V> head = table[keyIndex];
        if(head == null){
            return null;
        }
        if(head.key.equals(key)){
            table[keyIndex] = head.next;
            size--;
            return head.value;
        }

        //遍历链表
        Node<K,V> pre = head;
        Node<K,V> current = head.next;
        while (current != null){
            if(current.key.equals(key)){
                pre.next = current.next;
                size--;
                return current.value;
            }
            pre = pre.next;
            current = current.next;
        }

        return null;
    }

    public int size(){
        return size;
    }

    public int indexOf(Object key){
        return key.hashCode() & (table.length -1);
    }

    /**
     * 扩容
     */
    private void resizeIfNecessary(){
        if(this.size < table.length * 0.75){
            return;
        }
        Node<K,V>[] newTable = new Node[this.table.length * 2];
        for (Node<K, V> head : this.table) {
            if(head == null){
                continue;
            }
            Node<K,V> current = head;
            while (current != null){
                //链表头插法
                int newIndex = current.key.hashCode() & (newTable.length - 1);
                if(newTable[newIndex] ==null){
                    newTable[newIndex] = current;
                    Node<K,V> next = current.next;
                    current.next = null;
                    current = next;
                }else{
                    Node<K,V> next = current.next;
                    current.next = newTable[newIndex];
                    newTable[newIndex] = current;
                    current = next;
                }
            }

        }
        this.table = newTable;
        System.out.println("扩容量，当前扩容长度："+this.table.length);
    }

    class Node<K,V>{
        Node<K,V> next;
        K key;
        V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}
